#ifndef MY_ITERATOR_H_
#define MY_ITERATOR_H_

#include <type_traits>
#include <spw_config.h>
namespace spwstd {
// ===============================================================================
/* iterator base types
 * iterator tags; there are empty tags, used to distinguish different iterators.
 * 标志类，是具体iterator中IteratorCategory的值
 * 标准库中不同容器的数据结构，支持不同的访问操作能力，分成5类`
 * 1. 向前迭代器，只能向前迭代, 可读只写，多次扫描[多次遍历一个容器]
 * 2. 双向迭代器，可以向前迭代也可以向后迭代, 可读只写，多次扫描[多次遍历一个容器]
 * 3. 随机访问迭代器，不仅支持双向迭代，还支持任意偏移量，和随机访问。可读只写，多次扫描[多次遍历一个容器]
 * 4. 输入迭代器，只读不写，单遍扫描[遍历完一次，对所指原容器无效]，只能递增
 * 6. 输出迭代器，只写不读，单遍扫描，只能递增
 * */
struct InputIterTag {};
struct OnputIterTag {};
struct ForwardIterTag : public InputIterTag {};
struct BidirectionalIterTag: public ForwardIterTag {};
struct RandomAccessIterTag: public BidirectionalIterTag {};

// 相关类型迭代器

// ===============================================================================
/* IteratorTraits, 获取指定迭代器的迭代器特性，提供给使用者使用
 * ---- 对外接口 ----
 * */
template<typename Iter, typename = std::__void_t<>>
struct IteratorTraits_in {};

template<typename Iterator>
struct IteratorTraits_in<Iterator, 
    std::__void_t<typename Iterator::IteratorCategory,
                  typename Iterator::ValueType,
                  typename Iterator::DifferType,
                  typename Iterator::Refer>> 
{
    using IteratorCategory = typename Iterator::IteratorCategory;
    using ValueType = typename Iterator::ValueType;
    using DifferType = typename Iterator::DifferType;
    using Pointer = typename Iterator::Pointer;
    using Refer = typename Iterator::Refer;
};

template<typename Iter>
struct IteratorTraits: public IteratorTraits_in<Iter> { };
// 指针特化版, 为一些可以随机访问的容器特定，因为其内部实现的iterator就是元素的指针Pointer
// 没有实现成class，而专门特化. 例如，array, string, vector等
// 他们的Pointer已经具备他们iterator所有的功能
template<typename ValueT>
struct IteratorTraits<ValueT*> {
    using IteratorCategory = RandomAccessIterTag;
    using ValueType = ValueT;
    using DifferType = spwconfig::ptrdiff_t;
    using Pointer = ValueT*;
    using Refer = ValueT&;
};

template<typename ValueT>
struct IteratorTraits<const ValueT*> {
    using IteratorCategory = RandomAccessIterTag;
    using ValueType = ValueT;
    using DifferType =  spwconfig::ptrdiff_t;
    using Pointer = const ValueT*;
    using Refer = const ValueT&;
};

// ===============================================================================
/* iterator 支持的函数操作
 * distance, advance, next, prev
 * */
//////////// distance: 两个迭代器之间距离
// InputIterTag输入迭代器的距离计算
// 除了随机访问迭代器，输入迭代器，向前迭代器，双向迭代器都要一个一个访问，不能跳跃访问
template<typename InputIterator>
constexpr typename IteratorTraits<InputIterator>::DifferType
distance(InputIterator first, InputIterator last, InputIterTag) {
    typename IteratorTraits<InputIterator>::DifferType n = 0;
    while(first != last) {
        ++first;
        ++n;
    }
    return n;
}

// 随机访问迭代器distance
template<typename RadomAccessIterator>
constexpr typename IteratorTraits<RadomAccessIterator>::DifferType
distance(RadomAccessIterator first, RadomAccessIterator last, RandomAccessIterTag) {
    return last - first;
}

//* ---- 对外接口 ----
// 由__IteratorCategory()获得迭代器基础类型，由迭代器基础类型决定使用哪个__distance
template<typename InputIterator>
constexpr typename IteratorTraits<InputIterator>::DifferType
distance(InputIterator first, InputIterator last) {
    return distance(first, last, typename IteratorTraits<InputIterator>::IteratorCategory{}); 
}

//////////// advance 令指定迭代器向前移动n, 
// inputiterator和向前迭代器n不可为负
// 向前迭代器和inputiterator
template<typename InputIterator, typename Distance>
constexpr void advance(InputIterator& iter, Distance dis, InputIterTag) {
    // 如果dis < 0, 出错
    assert(dis >= 0);
    while(dis--) {
        ++iter;
    }
}

// 双向迭代器, n 可以负数
template<typename BidirectionalIterator, typename Distance>
constexpr void advance(BidirectionalIterator& iter, Distance dis, BidirectionalIterTag) {
    if (dis > 0) {
        while(dis--) {
            ++iter;
        }
    } else if (dis < 0) {
        while(dis++) {
            --iter;
        }
    }
}

// 随机访问迭代器
template<typename RadomAccessIterator, typename Distance>
constexpr void advance(RadomAccessIterator& iter, Distance dis, RandomAccessIterTag) {
    iter += dis;
}

//* ---- 对外接口 ----
template<typename InputIterator, typename Distance>
constexpr void advance(InputIterator& iter, Distance dis) {
    advance(iter, dis, typename IteratorTraits<InputIterator>::IteratorCategory{});
}
//* ---- 对外接口 ----
// next(iter, n) or next(iter)
// 返回的迭代器和传入迭代器，两个不同
template<typename InputIterator>
constexpr InputIterator 
next(InputIterator iter, typename IteratorTraits<InputIterator>::DifferType dis=1)
{
    spwstd::advance(iter, dis);
    return iter;
}
//* ---- 对外接口 ----
// prev(iter, n) or prev(iter)
// 返回的迭代器和传入迭代器，两个不同
template<typename BidirectionIterator>
constexpr BidirectionIterator 
prev(BidirectionIterator iter, typename IteratorTraits<BidirectionIterator>::DifferType dis=1)
{
    spwstd::advance(iter, -dis);
    return iter;
}

// ===============================================================================
/* iterator adaptery
 * 迭代器适配器， 不同类型迭代器
 * */
// 正常迭代器
// 把非类迭代器[如指针]，转换为类迭代器.
// Container的作用就是区别不同容器的迭代器
template<typename Iter, typename Container>
class NormalIterator {
protected:
    Iter curr;
    using IterType = IteratorTraits<Iter>; 

public:
    using IteratorCategory = typename IterType::IteratorCategory;
    using ValueType = typename IterType::ValueType;
    using DifferType = typename IterType::DifferType;
    using Pointer = typename IterType::Pointer;
    using Refer = typename IterType::Refer;

    constexpr NormalIterator(): curr{Iter()}{}
    explicit NormalIterator(const Iter& i): curr{i} {}

// iterator 要可以转换成 const_iterator
// curr 是指针，const type* curr = type* other, 所以iterator可以转换为const_iterator
    template<typename Iter2>
    NormalIterator(const NormalIterator<Iter2, 
        typename std::enable_if< 
            std::is_same<Iter2, typename Container::Pointer>::value, Container>::type>& i)
        : curr{ i.base() } {}

public:
    Refer operator*() const { return *curr; }

    Pointer operator->() const { return curr; }

    Refer operator[](DifferType n) const { return curr[n]; }

    NormalIterator& operator++() {
        ++curr;
        return *this;
    }

    NormalIterator operator++(int) {
        return NormalIterator(curr++);
    }


    NormalIterator& operator--() {
        --curr;
        return *this;
    }

    NormalIterator operator--(int) {
        return NormalIterator(curr--);
    }

    NormalIterator& operator+=(DifferType n)
    {
        curr += n; 
        return *this;
    }

    NormalIterator operator+(DifferType n) 
    {
        return NormalIterator(curr + n);
    }

    NormalIterator& operator-=(DifferType n)
    {
        curr -= n; 
        return *this;
    }

    NormalIterator operator-(DifferType n) 
    {
        return NormalIterator(curr - n);
    }

    const Iter& base() const { return curr; } 

};

// 可能是iterator 和const_iterator混合减
template<typename IterL, typename IterR, typename Container>
inline auto operator-(const NormalIterator<IterL, Container>& liter, 
                      const NormalIterator<IterR, Container>& riter)
-> decltype(liter.base() - riter.base())
{
    return liter.base() - riter.base();
}

template<typename Iter, typename Container>
inline typename NormalIterator<Iter, Container>::DifferType
operator-(const NormalIterator<Iter, Container>& liter,
          const NormalIterator<Iter, Container>& riter)
{
    return liter.base() - riter.base();
}

template<typename Iter, typename Container>
inline NormalIterator<Iter, Container>
operator+(typename NormalIterator<Iter, Container>::DifferType n,
          const NormalIterator<Iter, Container>& i)
{
    return NormalIterator<Iter, Container>(i.base()+n);
}

template<typename IterL, typename IterR, typename Container>
inline bool operator==(const NormalIterator<IterL, Container>& liter, 
                      const NormalIterator<IterR, Container>& riter)
{
    return liter.base() == riter.base();
}

template<typename Iter, typename Container>
inline bool operator==(const NormalIterator<Iter, Container>& liter,
                       const NormalIterator<Iter, Container>& riter)
{
    return liter.base() == riter.base();
}

template<typename IterL, typename IterR, typename Container>
inline bool operator!=(const NormalIterator<IterL, Container>& liter, 
                      const NormalIterator<IterR, Container>& riter)
{
    return liter.base() != riter.base();
}

template<typename Iter, typename Container>
inline bool operator!=(const NormalIterator<Iter, Container>& liter,
                       const NormalIterator<Iter, Container>& riter)
{
    return liter.base() != riter.base();
}

// TODO: 插入迭代器
} // namespace spwstd

namespace spwdetail {
template<typename InputIter>
using RequireInputIter
    = typename std::enable_if_t<
        std::is_convertible<
            typename spwstd::IteratorTraits<InputIter>::IteratorCategory, 
            spwstd::InputIterTag>::value>;
}
#endif
